package 校招笔试.阿里笔试;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/16 20:51
 */
public class 阿里315算法岗笔试 {
    /*
     算法面, 整体难度 不大
     */

    /*
    第一题，给一个长度为n数组,数字m，x。给一个操作，指定m个数字加x,n-m个数字乘x

    Q: 排序之后直接最小的用加法，大的用乘法

    第二题给一个数字n，求x，y 。x^y = n(异或) 且 |x-y| 最小

    Q: 按照bit位分割，y = 对应最高bit位为1的数，x=余下bit位为1，有边界条件需要处理（x,y>=1）

    第三题 给一个二维矩阵，可以从任意一点出发走k步，然后把这个k范围内的所有值加起来，问最大值是多少

    Q: 一眼dp，死活写不对，一个case都没过。佛了
     */


    /*
      第二题, 考察 这个 对 位运算的 一个 理解的
     */
    public int solutionTwo(int n){
        /*
         只要你明白, ^ (异或运算) 是 无进位 相加,
         明白这一点, 差不多这道题, 就出来了!
         x ^ 0 = x
         异或 满足 交换律  x ^ y = y ^ x
         x ^ x = 0
         */

        // 把最高位的 1 给 x , 剩下的 1 全给 y ,这样才能使 x,y 的差值最小!
        String s = Integer.toBinaryString(n);
        int x = (int) Math.pow(2,s.length() - 1),y = 0;
        for(int i = 1;i < s.length();i++){
            if(s.charAt(i) == '1'){
                y += (int)Math.pow(2,s.length() - i - 1);
            }
        }
        return x - y;
    }
}
